A quantum circuit to find discrete logarithms on ordinary binary elliptic curves in depth O(log^2 n)

摘要

Improving over an earlier construction by Kaye and Zalka, Maslov et al.describe an implementation of Shor's algorithm which can solve the discretelogarithm problem on binary elliptic curves in quadratic depth O(n^2). In thispaper we show that discrete logarithms on such curves can be found with aquantum circuit of depth O(log^2 n). As technical tools we introduce quantumcircuits for GF(2^n) multiplication in depth O(log n) and for GF(2^n) inversionin depth O(log^2 n).